XiaoHuang's Space
XiaoHuang's Space
XiaoHuang
May the force be with you.
『题解』BZOJ1036 [ZJOI2008]树的统计
Posted: Dec 11, 2019
Last Modified: Dec 13, 2019
This article was last modified 1853 days ago. The content of this post may be outdated!

Portal

Portal1: BZOJ

Portal2: Luogu

Description

一棵树上有nn个节点,编号分别为11nn,每个节点都有一个权值ww

我们将以下面的形式来要求你对这棵树完成一些操作:

  • CHANGE u t: 把结点uu的权值改为tt

  • QMAX u v: 询问从点uu到点vv的路径上的节点的最大权值;

  • QSUM u v: 询问从点uu到点vv的路径上的节点的权值和。

注意:从点uu到点vv的路径上的节点包括uuvv本身。

Input

输入文件的第一行为一个整数nn,表示节点的个数。

接下来n1n – 1行,每行22个整数aabb,表示节点aa和节点bb之间有一条边相连。

接下来一行nn个整数,第i个整数wiw_i表示节点ii的权值。

接下来11行,为一个整数qq,表示操作的总数。

接下来qq行,每行一个操作,以CHANGE u t或者QMAX u v或者QSUM u v的形式给出。

Output

对于每个QMAX或者QSUM的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

Solution

『题解』洛谷P3384 【模板】树链剖分

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int INF = 0x3f3f3f3f, MAXN = 400005;
struct EDGE {
    int u, v, nxt;
} edge[MAXN];
struct node {
    int l, r, w, Max, size, f;
} tree[MAXN];
int n, m, cnt, tot, a[MAXN], b[MAXN], son[MAXN], top[MAXN], idx[MAXN], dep[MAXN], head[MAXN], father[MAXN];
inline void addedge(int u, int v) {
    edge[++tot].u = u; edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot;
}
inline void dfs1(int x, int y) {//预处理
    tree[x].size = 1;
    for (int i = head[x]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == y) continue;
        dep[v] = dep[x] + 1;
        father[v] = x;
        dfs1(v, x);
        tree[x].size += tree[v].size;
        if (tree[v].size > tree[son[x]].size) son[x] = v;
    }
}
inline void dfs2(int now, int topf) {//预处理
    idx[now] = ++cnt;
    a[cnt] = now;
    top[now] = topf;
    if (son[now]) dfs2(son[now], topf);
    for (int i = head[now]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == father[now] || v == son[now]) continue;
        dfs2(v, v);
    }
}
inline void pushup(int root) {
    tree[root].w = tree[root << 1].w + tree[root << 1 | 1].w;
    tree[root].Max = max(tree[root << 1].Max , tree[root << 1 | 1].Max);
}
inline void build(int root, int l, int r) {
    if (l == r) {
        tree[root].w = tree[root].Max = b[a[l]];
        return ;
    }
    int mid = l + r >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    pushup(root);
}
inline void update(int root, int l, int r, int pos, int val) {
    int mid = l + r >> 1;
    if (l == r) {
        tree[root].w = tree[root].Max = val;
        return ;
    }
    if (pos <= mid) update(root << 1, l, mid, pos, val); else update(root << 1 | 1, mid + 1, r, pos, val);
    pushup(root);
}
inline int query_sum(int root, int l, int r, int ansl, int ansr) {
    int mid = l + r >> 1, ret = 0;
    if (ansl <= l && r <= ansr) return tree[root].w;
    if (ansl <= mid) ret += query_sum(root << 1, l, mid, ansl, ansr);
    if (ansr > mid) ret += query_sum(root << 1 | 1, mid + 1, r, ansl, ansr);
    pushup(root);
    return ret;
}
inline int query_max(int root, int l, int r, int ansl, int ansr) {
    int mid = l + r >> 1, ret = -INF;
    if (ansl <= l && r <= ansr) return tree[root].Max;
    if (ansl <= mid) ret = max(ret, query_max(root << 1, l, mid, ansl, ansr));
    if (ansr > mid) ret = max(ret, query_max(root << 1 | 1, mid + 1, r, ansl, ansr));
    pushup(root);
    return ret;
}
inline int tree_sum(int x, int y) {//树上求和
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += query_sum(1, 1, n, idx[top[x]], idx[x]);
        x = father[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ret += query_sum(1, 1, n, idx[y], idx[x]);
    return ret;
}
inline int tree_max(int x, int y) {//树上求最大值
    int ret = -INF;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = max(ret , query_max(1, 1, n, idx[top[x]], idx[x]));
        x = father[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ret = max(ret, query_max(1, 1, n, idx[y], idx[x]));
    return ret;
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    dep[1] = 1;
    father[1] = 1;
    dfs1(1, -1);
    dfs2(1, 1);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int opt, x, y, val;
        char s[6];
        scanf("%s%d%d", s, &x, &y);
        if (s[0] == 'C') update(1, 1, n, idx[x], y); else
        if (s[0] == 'Q' && s[1] == 'M') printf("%d\n", tree_max(x, y)); else printf("%d\n", tree_sum(x, y));
    }
    return 0;
}

Attachment

测试数据下载:https://www.lanzous.com/i5182ne

Article License: CC BY-NC-ND 4.0
Article Author: XiaoHuang
Powered By Valine
v1.5.2
  1. 1. Portal
  2. 2. Description
    1. 2.1. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution
  7. 7. Code
  8. 8. Attachment
Newer Post
『题解』BZOJ1798 [AHOI2009]维护序列
Older Post
『题解』洛谷P3384 【模板】树链剖分
Buy me a beer?
-->
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×